package com.learn.recursive;

/**
 * 在N*N的矩阵中，将N个皇后摆放在矩阵上，需要满足每个皇后之间都不共行，不共列，不共斜线
 */
public class NQueue {
    public int getMethods(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];
        return process(n, 0, record);
    }


    /**
     * index代表当前摆放到第几个皇后
     * record[i] 代表摆放在第i行，值为摆放在第几列
     *
     * @param n
     * @param index
     * @param record
     * @return 摆放的结果
     */
    public int process(int n, int index, int[] record) {
        if (index == n) {
            //index已经到达最后一行，说明有一种可能性
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(record, index, j)) {
                record[index] = j;
                //摆放在j位置，后续的所有可能性
                res += process(n, index + 1, record);
            }
        }
        return res;
    }


    /**
     * 判断摆放的位置是否有效
     *
     * @param record
     * @param i
     * @param j
     * @return
     */
    public boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            //在同一列或者行数之差等于列数之差
            if (record[k] == j || (Math.abs(i - k) == Math.abs(record[k] - j))) {
                return false;
            }
        }
        return true;
    }
}
